#!/usr/bin/python
#-*- coding:utf-8 -*-
# Description:  <C程序设计竞赛实训教程> 刘高军、何丽 编著 第11.4节：变换字符串(语法规则替换)
#          将源字符串src通过一系列规则rule变换成目标字符串tgt, 变换步骤不超过10
#  采用深度优先搜索策略, 递归函数实现

import numpy as np
from pprint import pprint
from collections import deque, namedtuple

item = namedtuple('item', ['s', 'count'])

def gen(isrc, tgt, rule):
    if isrc.s == tgt : return (isrc, True)
    if isrc.count >= 10 : return (isrc, False)
    for r in rule.keys():
        k = 0
        while k >= 0:
            k = isrc.s.find(r, k)
            if k >= 0:
                nxt_s = isrc.s[:k] + isrc.s[k:].replace(r, rule[r], 1)
                if len(nxt_s) <= 20:
                    t, flag = gen(item(nxt_s, isrc.count + 1), tgt, rule)
                    if flag: return (t, flag)
                k +=1
    return (isrc, False)

if __name__ == '__main__':
    src, tgt = 'a', 'aaaa'
    rule = {'a': 'a1122334455',
            '1122' : 'a',
            '334455' : '23a',
            '23' : 'a',
            }
    print gen(item(src, 0), tgt, rule)

    src, tgt = 'abcd', 'xyz'
    rule = {'abc': 'xu',
            'ud': 'y',
            'y': 'yz',
            }
    print gen(item(src, 0), tgt, rule)
    
